package leetcode_100;

import java.util.Arrays;

/**
 * 2018年5月17日 上午10:26:21
 * @author 周杨
 * describe : 利用Num1的空间  形成一个队列
 * MergeSortedArray_88 将两个有序数组组合在一起 成为一个新的有序数组  数组1会预留足够的空间让数组2进入
 */
public class MergeSortedArray_88 {

	public static void main(String[] args) {
		MergeSortedArray_88 test=new MergeSortedArray_88();
		int nums1[]={1,2,7,8,10,0,0,0,0,0};
		int nums2[]={2,3,6,9,11};
		
		test.merge1(nums1, 5, nums2, 5);

	}
	
	/**
	 * 直接将数组2放入数组1 然后排序数组1 低等解法 AC 14%
	 */
	public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(n==0)
            return ;
        for(int i=0;i<n;++i){
            nums1[i+m]=nums2[i];
        }
        Arrays.sort(nums1);
    }
	
	/**
	 * @param 将nums1的后部分利用起来 看做一个队列 如果队列里有值 则只比较队列里的值和Num2里的值 因为队列里的肯定比nums1当前的小 而且是有序的 
	 * AC 99.91%
	 */
	public void merge1(int[] nums1, int m, int[] nums2, int n) {
		 if (nums2 == null || nums1 == null) {
	            return;
	        } 
	        int i = m - 1, j = n - 1, index = nums1.length - 1;
	        while (i >=0 || j >= 0) {
	            if (i >= 0 && j >= 0) {
	                if (nums1[i] >= nums2[j]) {
	                    nums1[index] = nums1[i];
	                    i --;
	                } else {
	                    nums1[index] = nums2[j];
	                    j --;
	                }
	            } else if (i >= 0) {
	                nums1[index] = nums1[i];
	                    i --;
	            } else {
	                nums1[index] = nums2[j];
	                j --;
	            }
	            index --;
	        }
    }

}
